package leetcode.D500.T494;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class Solution {
    // 非dp解法
    static class Node {
        int value;
        int num;
        Node(){}
        Node(int v, int n) {
            value = v;
            num = n;
        }
    }
    public int findTargetSumWays(int[] nums, int target) {
        Queue<Node> queue = new LinkedList<>();
        int result = 0;
        queue.offer(new Node(0, 1));
        for (int i=0; i<nums.length; ++i) {
            int size = queue.size();
            Map<Integer, Integer> map = new HashMap<>();
            for (int j=0; j<size; ++j) {
                Node front = queue.poll();
                map.put(front.value + nums[i], map.getOrDefault(front.value + nums[i], 0) + front.num);
                map.put(front.value - nums[i], map.getOrDefault(front.value - nums[i], 0) + front.num);
            }
            if (i == nums.length-1) {
                result = map.getOrDefault(target, 0);
            } else {
                for (Map.Entry<Integer, Integer> entry : map.entrySet())
                    queue.offer(new Node(entry.getKey(), entry.getValue()));
            }
        }
        return result;
    }
}